﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace Console
{
    class Program
    {
        static void Main(string[] args)
        {

            //var d1 = Convert.ToDateTime("2017-04-16 08:55");
            //var d2 = Convert.ToDateTime("2017-04-17 17:22:50");

            //var inter1 = d2 - d1;
            //var inter2 = d1 - d2;

            //var mi = inter1.TotalMinutes;
            List<int> list1 = new List<int>() { 12, 3, 22, 9, 5, 55, 33, 21, 55,9,66,43, 44, 212, 7, 97, 66, 54 };


            List<int> list = new List<int>() { 9, 7, 6, 6 };
            var left = 0;
            var right = list.Count-1;
            QuickSort(ref list, left, right);
            abc(ref list1,left ,list1.Count-1);
            foreach (var item in list1)
            {
                System.Console.WriteLine(item);
            }
            var a = 1;
          System.  Console.Read();
          int i = 512;
          

        }
        #region 快速排序
        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="list">集合</param>
        /// <param name="left">开始序号</param>
        /// <param name="right">结束序号</param>
        private static void QuickSort(ref List<int> list,int left,int right )
        {
            if (left < right)
            {
                int i = left;
                int j = right;
                int middle = list[(left+right)/2];
                while (true)
                {
                    while (i<right&&list[i]<middle)
                    {
                        i++;
                    }
                    while (j > left && list[j] > middle)
                    {
                        j--;
                    }
                    if(i==j) break;
                    list[i] = list[i] + list[j];
                    list[j] = list[i] - list[j];
                    list[i] = list[i] - list[j];
                    if (list[i] == list[j]) j--;
                }

                QuickSort(ref list,left,i);
                QuickSort(ref list,i+1,right);
            }

        }
        private static void abc(ref List<int> n, int left, int right)
        {
            if (left < right)
            {
                var i = left;
                var j = right;
                var middle = n[(left + right) / 2];
                while (true)
                {
                    while (i < right && n[i] < middle)
                    {
                        i++;
                    }
                    while (j > left && n[j] > middle)
                    {
                        j--;
                    }
                    if (i == j) break;
                    n[i] = n[i] + n[j];
                    n[j] = n[i] - n[j];
                    n[i] = n[i] - n[j];
                    if (n[i] == n[j]) j--;
                }
                abc(ref n, left, i);
                abc(ref n, i + 1, right);
            }
        }

        #endregion

       

    }
}
